home *** CD-ROM | disk | FTP | other *** search
/ Games of Daze / Infomagic - Games of Daze (Summer 1995) (Disc 1 of 2).iso / x2ftp / books / tech / ssearcha.toc < prev    next >
Encoding:
Internet Message Format  |  1995-01-18  |  3.8 KB

  1. From: graham@sees.bangor.ac.uk (Graham A Stephen)
  2. Newsgroups: alt.books.technical
  3. Subject: Book Announcement
  4. Date: 22 Sep 1994 07:57:57 -0500
  5.  
  6. Lecture Notes Series on Computing
  7. STRING SEARCHING ALGORITHMS
  8. by Graham A Stephen (Univ Wales)
  9.  
  10.  
  11. String searching is a subject of both theoretical and practical
  12. interest in computer science.  This book presents a bibliographic 
  13. overview of the field and an anthology of detailed descriptions of
  14. the principal algorithms available.  The aim is twofold: on the
  15. one hand, to provide an easy-to-read comparison of the available 
  16. techniques in each area, and on the other, to furnish the reader
  17. with a reference to in-depth descriptions of the major algorithms. 
  18. Topics covered include methods for finding exact and approximate 
  19. string matches, calculating 'edit' distances between strings, 
  20. finding common sequences and finding the longest repetitions within 
  21. strings.  For clarity, all the algorithms are presented in a uniform 
  22. format and notation.
  23.  
  24. Contents: Introduction; String Matching; String Distance and 
  25. Common Sequences; Suffix Trees; Approximate String Matching; 
  26. Repeated Substrings.
  27.  
  28. Readership: Computer scientists, software developers and
  29. computational biologists.
  30.  
  31. 250pp (approx)       Pub date: October 1994
  32. ISBN 981-02-1829-X   US$ 34 / UK pounds 25
  33.  
  34.  
  35. For further information, please contact the Marketing Department,
  36. World Scientific Publishing Co Pte Ltd at fax no: (65) 382 5919 
  37. or e-mail address: worldscp@singnet.com.sg 
  38.  
  39. =================================================================
  40.  
  41. DETAILED CONTENTS
  42.  
  43. 1  Introduction
  44.  
  45. 2  String Matching
  46.    2.1  Overview
  47.         2.1.1  Brute Force
  48.         2.1.2  Knuth-Morris-Pratt and Boyer-Moore Approaches
  49.         2.1.3  Hashing Functions
  50.         2.1.4  Comparative Performance
  51.         2.1.5  Popularity
  52.         2.1.6  Multiple-String Searches
  53.    2.2  Algorithms in Detail
  54.         2.2.1  Brute Force
  55.         2.2.2  Knuth-Morris-Pratt
  56.         2.2.3  Boyer-Moore
  57.         2.2.4  Boyer-Moore-Horspool
  58.         2.2.5  Sunday --- Quick Search, Maximal Shift, and Optimal Mismatch
  59.         2.2.6  Hume and Sunday --- Tuned Boyer-Moore and Least Cost
  60.         2.2.7  Harrison
  61.         2.2.8  Karp-Rabin
  62.    2.3  Further Reading
  63.  
  64. 3  String Distance and Common Sequences
  65.    3.1  Overview
  66.         3.1.1  String Distance Measures
  67.         3.1.2  String Distance and Longest Common Subsequence
  68.         3.1.3  Comparative Performance
  69.         3.1.4  Related Problems
  70.    3.2  Algorithms in Detail
  71.         3.2.1  Wagner-Fischer
  72.         3.2.2  Hirschberg
  73.         3.2.3  Hunt-Szymanski
  74.         3.2.4  Masek-Paterson
  75.         3.2.5  Ukkonen
  76.         3.2.6  Heaviest Common Subsequence
  77.    3.3  Further Reading
  78.  
  79. 4  Suffix Trees
  80.    4.1  Overview
  81.         4.1.1  Suffix Tries
  82.         4.1.2  From Suffix Trie to Suffix Tree
  83.    4.2  Algorithms in Detail
  84.         4.2.1  Brute Force
  85.         4.2.2  McCreight
  86.         4.2.3  Ukkonen
  87.    4.3  Further Reading
  88.  
  89. 5  Approximate String Matching
  90.    5.1  Overview
  91.         5.1.1  String Matching with k Mismatches
  92.         5.1.2  String Matching with k Differences
  93.         5.1.3  String Matching with Don't-Cares
  94.         5.1.4  Application Areas
  95.         5.1.5  Dedicated Hardware and Parallel Algorithms
  96.    5.2  Algorithms in Detail
  97.         5.2.1  Landau-Vishkin k-mismatches
  98.         5.2.2  Shift-Add
  99.         5.2.3  Tarhio-Ukkonen k-mismatches
  100.         5.2.4  Baeza-Yates--Perleberg k-mismatches
  101.         5.2.5  Dynamic Programming k-differences
  102.         5.2.6  Landau-Vishkin k-differences
  103.         5.2.7  Chang-Lawler k-differences
  104.         5.2.8  Chang-Lampe k-differences
  105.         5.2.9  Wu-Manber k-differences
  106.    5.3  Further Reading
  107.  
  108. 6  Repeated Substrings
  109.    6.1  Overview
  110.         6.1.1  Repetitions
  111.         6.1.2  Longest Repeated Substrings
  112.    6.2  Algorithms in Detail
  113.         6.2.1  Brute Force
  114.         6.2.2  Suffix Trees
  115.  
  116. A  Asymptotic Notation
  117.  
  118. B  String Symbology
  119.  
  120. C  Glossary
  121.  
  122. D  Bibliography
  123.  
  124. Index
  125.  
  126.  
  127.  
  128.